package com.shm.netease;

import java.util.Scanner;

/**
 * 蛇形方阵
 * 方阵的值从1开始，由外层开始先顺时针在逆时针交替向内层螺旋排列
 * @author SHM
 */
public class Main_Snake {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int i = Integer.parseInt(s);
        for (int j = 0; j < i; j++) {
            String str = sc.nextLine();
            String[] ss = str.split(" ");
            int n = Integer.parseInt(ss[0]);
            System.out.println("n="+n);
            int m = Integer.parseInt(ss[1]);
            System.out.println("m="+m);
            for (int k = 0; k < m; k++) {
                String str1 = sc.nextLine();
                String[] ss1 = str1.split(" ");
                int x = Integer.parseInt(ss1[0]);
                System.out.println("x="+x);
                int y = Integer.parseInt(ss1[1]);
                System.out.println("y="+y);
                int data = getData_1(n, m, x, y);
                System.out.println(data);
            }
        }
    }

    public static int getData_1(int n,int m,int x,int y){
        int data = 0;
        int[][] matrix = new int[n][n];
        int up = 0;
        int down = n-1;
        int left = 0;
        int right = n-1;
//        int tar = n*n;
        while (true){
            //上
            for (int i = left; i <=right ; i++) {
                matrix[up][i]=++data;
            }
            up++;
            if (up>down){
                break;
            }
            //右
            for (int j = up; j <= down; j++) {
                matrix[j][right]=++data;
            }
            right--;
            if (right<left){
                break;
            }
            //下
            for (int i = right; i >=left ; i--) {
                matrix[down][i]=++data;
            }
            down--;
            if (down<up){
                break;
            }
            //左
            for (int j = down; j >= up; j--) {
                matrix[j][left]=++data;
            }
            left++;
            if (left>right){
                break;
            }

            for (int j = up; j <= down; j++) {
                matrix[j][left]=++data;
            }
            left++;
            if (left>right){
                break;
            }

            for (int i = left; i <=right ; i++) {
                matrix[down][i]=++data;
            }
            down--;
            if (down<up){
                break;
            }

            for (int j = down; j >= up; j--) {
                matrix[j][right]=++data;
            }
            right--;
            if (right<left){
                break;
            }

            for (int i = right; i >=left ; i--) {
                matrix[up][i]=++data;
            }
            up++;
            if (up>down){
                break;
            }
        }
        return matrix[x][y];
    }


    public static int getData(int n,int m,int x,int y){
        int left = 0,right = n-1,up=0,down=n-1;
        int[][] matrix = new int[n][n];
        int num=1,tar=n*n;
        boolean flag = true;
        while (num<=tar) {
            if (flag) {
                flag = false;
                for (int i = left; i <= right; i++) {
                    matrix[up][i] = num++;
                }
                up++;
                for (int i = up; i <= down; i++) {
                    matrix[i][right] = num++;
                }
                right--;
                for (int i = right; i >= left; i--) {
                    matrix[down][i] = num++;
                }
                down--;
                for (int i = down; i >= up; i--) {
                    matrix[i][left] = num++;
                }
                left++;
            }else {
                flag = true;
                for (int i = up; i <= down; i++) {
                    matrix[i][left] = num++;
                }
                left++;
                for (int i = left; i <= right; i++) {
                    matrix[down][i] = num++;
                }
                down--;
                for (int i = down; i >= up; i--) {
                    matrix[i][right] = num++;
                }
                right--;
                for (int i = right; i >= left; i--) {
                    matrix[up][i] = num++;
                }
                up++;
            }
        }
        return matrix[x][y];
    }
}
